#include <glf/mem/ephemeralAllocator.h>
#include <glf/core/atomic.h>
#include <glf/core/thread.h>
#include <glf/math/functions.h>

#include <vector>

namespace glf
{

namespace
{

class EphemeralMemoryBlock;

/************************************************************************/
/* EphemeralAllocator													*/
/************************************************************************/
class EphemeralAllocatorImpl
{
public:
	static EphemeralAllocatorImpl& GetInstance();

	void* Alloc(size_t size);
	static void Free(void* ptr);

	void NextMemoryBlock();

	EphemeralMemoryBlock* m_MemoryBlock;
	char* m_Cursor;
	char* m_Tail;
};


/************************************************************************/
/* EphemeralMemoryBlockAllocator                                        */
/************************************************************************/
class EphemeralMemoryBlockAllocator
{
public:
	EphemeralMemoryBlockAllocator();

	EphemeralMemoryBlock* Create();

	void Release(EphemeralMemoryBlock* memoryBlock);

	void CleanupFreeBlocks();

	static EphemeralMemoryBlockAllocator& GetInstance();

protected:
	friend class EphemeralMemoryBlock;
	void Push(EphemeralMemoryBlock* memoryBlock);

	EphemeralMemoryBlock* Pop();

	size_t m_BlockSize;
	Atomic32 m_Available;
	Atomic32 m_PopListIterator;
	Atomic32 m_PushListIterator;

	struct List
	{
	public:
		List()
			: m_Ticket(0)
			, m_Serving(0)
			, m_Head(NULL)
		{	
		}

		void Push(EphemeralMemoryBlock* block);

		EphemeralMemoryBlock* TryPop();

		EphemeralMemoryBlock* Pop();

	private:
		Atomic32 m_Ticket;
		Atomic32 m_Serving;
		EphemeralMemoryBlock* m_Head;

		void Lock();
		void Unlock();
	};

	std::vector<List> m_FreeMemoryBlockLists;

protected:
	static EphemeralMemoryBlockAllocator Instance;
};

/************************************************************************/
/* EphemeralMemoryBlock                                                 */
/************************************************************************/
class EphemeralMemoryBlock
{
public:
	static EphemeralMemoryBlock* Alloc(size_t size);

	static void Free(EphemeralMemoryBlock* block);

	//static EphemeralMemoryBlock& cast(void* block);

	void Grab();

	void Drop();

	void* GetBegin();

	void* GetEnd();

	size_t GetSize() const;


protected:
	EphemeralMemoryBlock(size_t size);

	friend class EphemeralMemoryBlockAllocator;

	void SetNext(EphemeralMemoryBlock* next);

	EphemeralMemoryBlock* GetNext();

protected:
	

	EphemeralMemoryBlock* m_Next;
	Atomic32 m_ReferenceCounter;
	const size_t m_Size;
	char m_Begin[1];
};

/************************************************************************/
/* EphemeralAllocation                                                  */
/************************************************************************/
class EphemeralAllocation
{
public:
	EphemeralAllocation(EphemeralMemoryBlock* memoryBlock);

	~EphemeralAllocation();

	operator void* ();

	static EphemeralAllocation* Alloc(void* place, EphemeralMemoryBlock* memoryBlock);

	static void Free(void* ptr);

	static size_t GetSizeOf(size_t bufferSize);

protected:
	static EphemeralAllocation* Get(void* ptr);
	void* operator new (size_t sz, void* v)
	{
		return v;
	}
	void* operator new(size_t); // Must not be available
	void operator delete(void*)
	{
		GLF_ASSERTMSG(false, "EphemeralAllocation::operator delete should never be called.")
	}

private:
	EphemeralMemoryBlock* m_MemoryBlock;
	char m_Ptr[1];
};


/************************************************************************/
/* EphemeralMemoryBlockAllocator                                        */
/************************************************************************/
EphemeralMemoryBlockAllocator EphemeralMemoryBlockAllocator::Instance;

EphemeralMemoryBlockAllocator::EphemeralMemoryBlockAllocator()
	: m_BlockSize(1024)
{
	int requestedQueues = 16; 
	// Could be change for something close to the number of hardware thread
	requestedQueues = 1 << (Sqrt(requestedQueues));
	GLF_ASSERTMSG(requestedQueues == 1 << (Sqrt(requestedQueues)), "Must be power of 2");
	m_FreeMemoryBlockLists.resize(requestedQueues); 
}

EphemeralMemoryBlock* EphemeralMemoryBlockAllocator::Create()
{
	EphemeralMemoryBlock* memoryBlock;
	memoryBlock = Pop();
	memoryBlock->Grab();
	return memoryBlock;
}

void EphemeralMemoryBlockAllocator::Release(EphemeralMemoryBlock* memoryBlock)
{
	if(memoryBlock)
	{
		memoryBlock->Drop();
	}
}

void EphemeralMemoryBlockAllocator::CleanupFreeBlocks()
{
	while(m_Available)
	{
		EphemeralMemoryBlock* memoryBlock;
		memoryBlock = Pop();
		EphemeralMemoryBlock::Free(memoryBlock);
		memoryBlock->Drop();
	}
}

EphemeralMemoryBlockAllocator& EphemeralMemoryBlockAllocator::GetInstance()
{
	return Instance;
}


void EphemeralMemoryBlockAllocator::Push(EphemeralMemoryBlock* memoryBlock)
{
	// Push can be done out of order but this 
	// system guaranty a uniform spread of the block
	// in each internal list
	int listID = ++m_PushListIterator;
	listID %= m_FreeMemoryBlockLists.size();
	List& list = m_FreeMemoryBlockLists[listID];
	list.Push(memoryBlock);

	// We change availability as late as we can
	++m_Available;
}	

bool TryDecrease(Atomic32& counter)
{
	// decrease counter only if higher than 0
	int available = counter;
	while(available != 0)
	{
		if(available == counter.compareAndSwap(available - 1, available))
		{
			// Decrease succeed
			break;
		}
		else
		{
			// Try again
			available = counter;
		}
	}
	return available != 0;
}

EphemeralMemoryBlock* EphemeralMemoryBlockAllocator::Pop()
{
	if(!TryDecrease(m_Available))
	{
		// It was empty, we won't try again let allocate a new block instead
		return EphemeralMemoryBlock::Alloc(m_BlockSize);
	}

	// We succeed to decrease the availability so we should be able to pop
	// something in one of the list set

	// Select a list
	int listID = ++m_PopListIterator;
	listID %= m_FreeMemoryBlockLists.size();
	List& list = m_FreeMemoryBlockLists[listID];

	// Since push may be done out of order, pop may be done in a list 
	// that is about to be filled. The pop must not fail.
	return list.Pop();
}

/************************************************************************/
/*  EphemeralMemoryBlockAllocator::List                                 */
/************************************************************************/
	
void EphemeralMemoryBlockAllocator::List::Push(EphemeralMemoryBlock* block)
{
	Lock();
	block->SetNext(m_Head);
	m_Head = block;
	Unlock();
}

EphemeralMemoryBlock* EphemeralMemoryBlockAllocator::List::TryPop()
{
	EphemeralMemoryBlock* block = NULL;

	Lock();
	block = m_Head;
	if(block)
	{
		m_Head = m_Head->GetNext();
	}
	Unlock();
	if(block == NULL)
	{
		return NULL;
	}
	else
	{
		block->SetNext(NULL);
		return block;
	}
}

EphemeralMemoryBlock* EphemeralMemoryBlockAllocator::List::Pop()
{
	EphemeralMemoryBlock* block = NULL;

	do
	{
		block = TryPop();
		if(block == NULL)
		{
			Thread::Sleep(0);
		}
	} while(block == NULL);

	return block;
}

void EphemeralMemoryBlockAllocator::List::Lock()
{
	int ticketID = m_Ticket++;
	while(m_Serving != ticketID)
	{
		Thread::Sleep(0);
	}
}

void EphemeralMemoryBlockAllocator::List::Unlock()
{
	++m_Serving;
}

/************************************************************************/
/* EphemeralMemoryBlock                                                 */
/************************************************************************/
EphemeralMemoryBlock* EphemeralMemoryBlock::Alloc(size_t size)
{
	EphemeralMemoryBlock* memoryBlock = (EphemeralMemoryBlock*) new char[size];
	new (memoryBlock) EphemeralMemoryBlock(size);
	return memoryBlock;
}

void EphemeralMemoryBlock::Free(EphemeralMemoryBlock* block)
{
	delete[] (char*)block;
}

EphemeralMemoryBlock::EphemeralMemoryBlock(size_t size)
	: m_ReferenceCounter(0)
	, m_Size(size - ((char*)&m_Begin - (char*)this))
{
}

void EphemeralMemoryBlock::Grab()
{
	++m_ReferenceCounter;
}

void EphemeralMemoryBlock::Drop()
{
	int counter = --m_ReferenceCounter;
	if(counter == 0)
	{
		// We should not face any concurrent issue on the counter
		// since the counter is increased by the owner as long as there's
		// space for other allocation (Grab).
		// The ref count can't be 0 during the allocation process
		// Once fulfilled, the allocator drop it and we wont have 
		// further Grab until the block is fully released.
		EphemeralMemoryBlockAllocator::GetInstance().Push(this);
	}
}

void* EphemeralMemoryBlock::GetBegin()
{
	return (void*)m_Begin;
}

void* EphemeralMemoryBlock::GetEnd()
{
	return (void*)(m_Begin + m_Size);
}

size_t EphemeralMemoryBlock::GetSize() const
{
	return m_Size;
}

void EphemeralMemoryBlock::SetNext(EphemeralMemoryBlock* next)
{
	m_Next = next;
}

EphemeralMemoryBlock* EphemeralMemoryBlock::GetNext()
{
	return m_Next;
}

/************************************************************************/
/* EphemeralAllocation                                                  */
/************************************************************************/
EphemeralAllocation::EphemeralAllocation(EphemeralMemoryBlock* memoryBlock)
	: m_MemoryBlock(memoryBlock)
{
	m_MemoryBlock->Grab();
}

EphemeralAllocation::~EphemeralAllocation()
{
	EphemeralMemoryBlock* memoryBlock = m_MemoryBlock;
	m_MemoryBlock = NULL;
	// Memory block may be release and attributed to someone else so this
	// call must be the last one.
	memoryBlock->Drop();  
}

EphemeralAllocation::operator void* ()
{
	return m_Ptr;
}

EphemeralAllocation* EphemeralAllocation::Alloc(void* place, EphemeralMemoryBlock* memoryBlock)
{
	return new (place) EphemeralAllocation(memoryBlock);
}

void EphemeralAllocation::Free(void* ptr)
{
	EphemeralAllocation* allocation = Get(ptr);
	allocation->~EphemeralAllocation();
}

size_t EphemeralAllocation::GetSizeOf(size_t bufferSize)
{
	size_t requestedSize = bufferSize + sizeof(EphemeralMemoryBlock*);
	requestedSize = GLF_ROUNDUP(requestedSize, 4);
	return requestedSize;
}

EphemeralAllocation* EphemeralAllocation::Get(void* ptr)
{
	EphemeralAllocation* allocation = static_cast<EphemeralAllocation*>(ptr);
	const int offset = (char*)&allocation->m_Ptr - (char*)allocation;
	allocation = reinterpret_cast<EphemeralAllocation*>((char*)allocation - offset);
	return allocation;
}

/************************************************************************/
/* EphemeralAllocator                                                   */
/************************************************************************/
GLF_DECLARE_TLS(EphemeralAllocatorImpl, EphemeralAllocatorInstance, extern);
GLF_DEFINE_TLS(EphemeralAllocatorImpl, EphemeralAllocatorInstance) = { {NULL, NULL, NULL} };


void* EphemeralAllocatorImpl::Alloc(size_t size)
{
	size_t requestedSize = EphemeralAllocation::GetSizeOf(size);

	if(m_Cursor + requestedSize > m_Tail)
	{
		NextMemoryBlock();
	}

	GLF_ASSERTMSG(requestedSize <= m_MemoryBlock->GetSize(), "Add support for allocation with size higher than the block size");

	EphemeralAllocation* ptr = EphemeralAllocation::Alloc(m_Cursor, m_MemoryBlock);

	m_Cursor += requestedSize;	
	return *ptr;
}

void EphemeralAllocatorImpl::Free(void* ptr)
{
	EphemeralAllocation::Free(ptr);
}

EphemeralAllocatorImpl& EphemeralAllocatorImpl::GetInstance()
{
	return EphemeralAllocatorInstance.get();
}

void EphemeralAllocatorImpl::NextMemoryBlock()
{
	EphemeralMemoryBlockAllocator::GetInstance().Release(m_MemoryBlock);
	m_MemoryBlock = EphemeralMemoryBlockAllocator::GetInstance().Create();
	m_Cursor = (char*)m_MemoryBlock->GetBegin();
	m_Tail = (char*)m_MemoryBlock->GetEnd();
}

} // end of namespace anonymous


void* allocateEphemeralAllocation(size_t size)
{
	return EphemeralAllocatorImpl::GetInstance().Alloc(size);
}

void freeEphemeralAllocation(void* ptr)
{
	EphemeralAllocatorImpl::GetInstance().Free(ptr);
}

void cleanupEphemeralFreeBlocks()
{
	EphemeralMemoryBlockAllocator::GetInstance().CleanupFreeBlocks();
}


} // end namespace glf